/******************************************************************************
//             INTEL CORPORATION PROPRIETARY INFORMATION
//  This software is supplied under the terms of a license agreement or
//  nondisclosure agreement with Intel Corporation and may not be copied
//  or disclosed except in accordance with the terms of that agreement.
//    Copyright(c) 2000 - 2001 Intel Corporation. All Rights Reserved.
//
//  VSS: 
//     $Workfile: $
//     $Revision: $
//     $Date:     $
//     $Archive:  $
//
//  Description:
//      Intel(R) Integrated Performance Primitives - JPEG Helper file.
//      This file contains functions to generate huffman table SPEC 
//      and optimized huffman encoding/decoding tables.
//
//  History:
//     Date         Author        Changes
//     2001/2/1     Jerry Hu      Created (Version 0.2, K1, k4 in T.81)
//
********************************************************************************/
#include "_ippjpeg.h"

const Ipp8u _nIppIZigZagIndex[64] =
{
    0,  1,  8, 16,  9,  2,  3, 10,
    17, 24, 32, 25, 18, 11,  4,  5,
    12, 19, 26, 33, 40, 48, 41, 34,
    27, 20, 13,  6,  7, 14, 21, 28,
    35, 42, 49, 56, 57, 50, 43, 36,
    29, 22, 15, 23, 30, 37, 44, 51,
    58, 59, 52, 45, 38, 31, 39, 46,
    53, 60, 61, 54, 47, 55, 62, 63
};

/******************************************************************************
// Name:             ippiGetZigZagTable
// Description:      Get ZigZag table.
// Input Arguments: 
//                   N/A          
// Output Arguments:
//   ppIZigZagTable: Identifies the pointer to the zigzag table.
//
// Remarks:          None.
//
// Returns:         
//    IPP_STATUS_OK: Succeeds.
******************************************************************************/
IPPFUN(IppStatus, ippiGetZigZagTable) (const Ipp8u **ppIZigZagTable)
{
    _IPP_CHECK_ARG(NULL!=ppIZigZagTable);
    _IPP_CHECK_ARG(NULL!=*ppIZigZagTable);

    *ppIZigZagTable=_nIppIZigZagIndex;

    return IPP_STATUS_OK;
}

/******************************************************************************
// Name:             ippiHuffmanTableSpecInit_JPEG_8u
// Description:      Generate huffman table SPEC accordingto K1 - k4 in T.81
// Input Arguments: 
//            pFreq: Identifies frequency statistic
//        pCodeSize: Identifies code size buffer for internal usage. The length is 258.
//          pOthers: Identifies others buffer for internal usage. The length is 258.
//            pBits: Identifies bits buffer for internal usage. The length is 34.
//
// Output Arguments:
//        pHuffBits: Identifies huffman bits buffer.
//       pHuffValue: Identifies huffman value buffer.
//
// Remarks:          None.
//
// Returns:         
//    IPP_STATUS_OK: Succeeds.
******************************************************************************/
IPPFUN(IppStatus, ippiHuffmanTableSpecInit_JPEG_8u) (int *pFreq,
                                                     int *pCodeSize,
                                                     int *pOthers,
                                                     Ipp8u *pBits,
                                                     Ipp8u* pHuffBits,
                                                     Ipp8u* pHuffValue)
{
    int   i;
    int   j;
    int   k;
    int   min;
    int   V1;
    int   V2;
    int   *FREQ=pFreq;
    int   *OTHERS=pOthers;
    int   *CODESIZE=pCodeSize;
    Ipp8u *BITS=pBits;

    _IPP_CHECK_ARG((NULL!=pFreq)&&(NULL!=pCodeSize)&&(NULL!=pOthers)&&(NULL!=pBits));
    _IPP_CHECK_ARG(NULL!=pHuffBits && NULL!=pHuffValue);

    for (i=0; i<257; i++) {
        CODESIZE[i]=0;
        OTHERS[i] = -1;
    }

    for (i=0; i<33; i++) {
        BITS[i]=0;
    }

    FREQ[256] = 1;

    /* Procedure to find huffman code size */ 
    //do {
    for (;;) {
    /* find V1 for least value of FREQ[V1] > 0 */
        V1 = -1;
        min  = (int)1000000000L;

        for (i = 0; i < 257; i++) {
            if ((0!=FREQ[i])&&(min>=FREQ[i])) {
                min = FREQ[i];
                V1 = i;
          }
        }

    /* find V2 for next least value of FREQ[V2] > 0 */
        V2   = -1;
        min  = (int)1000000000L;

        for (i = 0; i < 257; i++) {
            if ((0!=FREQ[i])&&(min>=FREQ[i])&&(i!=V1)) {
                min = FREQ[i];
                V2 = i;
          }
        }

        if (-1==V2) {
           break;
        }

        FREQ[V1] = FREQ[V1] + FREQ[V2];
        FREQ[V2] = 0;

        for (;;) {
          CODESIZE[V1]++;
          if (-1==OTHERS[V1]) {
              break;
          } 
          V1 = OTHERS[V1];
        }
/*
        do {
          CODESIZE[V1]++;
          if (-1==OTHERS[V1]) {
              break;
          } 
          V1 = OTHERS[V1];
        } while (TRUE);
*/
        OTHERS[V1] = V2;

        for (;;) {
          CODESIZE[V2]++;
          if (-1==OTHERS[V2]) {
              break;
          } 
          V2 = OTHERS[V2];
        }
/*
        do {
          CODESIZE[V2]++;
          if (-1==OTHERS[V2]) {
              break;
          } 
          V2 = OTHERS[V2];
        } while(TRUE);
*/
//    } while(TRUE);
    }

    /* Procedure to find the number of codes of each size */

    i = 0;
    do {
      if (0!=CODESIZE[i]) {
         BITS[ CODESIZE[i] ]++;
      }
      i++;
    } while(i < 257);

    /* Procedure for limiting code length to 16 bits */

    i = 32;

    for (;;) {
    //do {
      if (0<BITS[i]) {
          j = i - 1;
          do {
            j = j - 1;
          } while(0==BITS[j]);

          BITS[i]     = (Ipp8u)(BITS[i] - 2);
          BITS[i - 1] = (Ipp8u)(BITS[i - 1] + 1);
          BITS[j + 1] = (Ipp8u)(BITS[j + 1] + 2);
          BITS[j]     = (Ipp8u)(BITS[j] - 1);
      } else {
          i = i - 1;
          if (15!=i) {
              continue;
          }
          while (0==BITS[i]) {
              i--;
          }
          BITS[i] = (Ipp8u)(BITS[i] - 1);
          break;
          
      }
    //} while(TRUE);
    }

    for (i=0; i<16; i++) {
        pHuffBits[i]=BITS[i];
    }

    /* Sorting of input values according to code size */

    i = 1;
    k = 0;

    do {
        j = 0;
        do {
            if (CODESIZE[j] == i) {
               pHuffValue[k] = (Ipp8u)j;
               k = k + 1;
            }
            j = j + 1;
        } while (255>=j);
        i = i + 1;
    } while(i<=32);

    return IPP_STATUS_OK;
}
 
/******************************************************************************
// Name:             ippiEncodeHuffmanTableInit_JPEG_8u
// Description:      Generate huffman table.
// Input Arguments: 
//        pHuffBits: Identifies huffman bits buffer.
//       pHuffValue: Identifies huffman value buffer.
//
// Output Arguments:
//       pHuffTable: Identifies a IppJPEGEnHuffTable data structure.
//
// Remarks:          None.
//
// Returns:         
//    IPP_STATUS_OK: Succeeds.
******************************************************************************/
IPPFUN(IppStatus, ippiEncodeHuffmanTableInit_JPEG_8u) (const Ipp8u *pHuffBits,
                                                       const Ipp8u *pHuffValue,
                                                       IppJPEGEnHuffTable *pHuffTable)

{
    Ipp32u code;
    Ipp16u huffcode[258];
    Ipp8u  huffsize[258];
    int i,j,k,lastk,si, L;

    Ipp8u *pHuffSize=pHuffTable->huffSize;
    Ipp16u *pHuffCode=pHuffTable->huffCode;

    _IPP_CHECK_ARG(NULL!=pHuffBits && NULL!=pHuffValue);
    _IPP_CHECK_ARG(NULL!=pHuffTable);

    /* Init table */
    for (i = 0; i < 256; i++){ 
        huffsize[i]  = 0;
        huffcode[i]  = 0;
        pHuffSize[i] = 0;
        pHuffCode[i] = 0;
    }

    /* 
    // Make table of Huffman code length for each symbol.
    // Note that this is in code-length order. 
    */
    for( k=0, i=1; i<17; i++ ){
        L=(int)pHuffBits[i-1];
        for (j = 1; j <= L; j++){
            huffsize[k++] = (Ipp8u) i;
        }
    }

    huffsize[k] = 0;
    lastk       = k;

    /* 
    // Generate the codes themselves.
    // Note that this is in code-length order. 
    */
    k = 0;
    code = 0;
    si = huffsize[0];
    while (huffsize[k]) {
        while (((int) huffsize[k]) == si) {
              huffcode[k++] = (Ipp16u)code;
              code++;
        }
        code <<= 1;
        si++;
    }

    /* 
    // Generate encoding tables. 
    // These are code and size indexed by symbol value 
    // Set any codeless symbols to have code length 0;
    // this allows emit_bits to detect any attempt to emit such symbols.
    */
    for (k = 0; k<lastk; k++){
        i = (int)pHuffValue[k];
        pHuffSize[i] = huffsize[k];
        pHuffCode[i] = huffcode[k];
    }

    return IPP_STATUS_OK;
}

/******************************************************************************
// Name:             ippiDecodeHuffmanTableInit_JPEG_8u
// Description:      Generate huffman table.
// Input Arguments: 
//        pHuffBits: Identifies huffman bits buffer.
//       pHuffValue: Identifies huffman value buffer.
//
// Output Arguments:
//       pHuffTable: Identifies a IppJPEGDeHuffTable data structure.
//
// Remarks:          None.
//
// Returns:         
//    IPP_STATUS_OK: Succeeds.
******************************************************************************/
IPPFUN(IppStatus, ippiDecodeHuffmanTableInit_JPEG_8u) (const Ipp8u *pHuffBits,
                                                       const Ipp8u *pHuffValue,
                                                       IppJPEGDeHuffTable *pHuffTable)
{
    Ipp16u  code;
    int  i, j, p, k, si;

    Ipp16u  huffcode[257];
    Ipp8u   huffsize[257];
    int     lookbits, ctr;

    _IPP_CHECK_ARG(NULL!=pHuffBits && NULL!=pHuffValue);
    _IPP_CHECK_ARG(NULL!=pHuffTable);

    /* 
    // Make table of Huffman code length for each symbol.
    // Note that this is in code-length order. 
    */
    for (p=0, i=1; i<17; i++) {
        k = (int)pHuffBits[i-1];
        for (j = 1; j <= k; j++) {
             huffsize[p]=(Ipp8u)i;
             p++;
        }
    }

    huffsize[p] = 0;

    /* 
    // Generate the codes themselves.
    // Note that this is in code-length order. 
    */
    p  = 0;
    code = 0;
    si = huffsize[0];

    while (huffsize[p]) {
        while (((int)huffsize[p]) == si) {
            huffcode[p++] = code;
            code++;
        }
        code<<=1;
        si++;
    }

    for (j=0; j<17; j++) {
        pHuffTable->valptr[j]  = 0;
        pHuffTable->mincode[j] = 0;
        pHuffTable->maxcode[j] = 0;
    }

    /* F.15 */
    for (p=0, j=1; j<17; j++) {
        k=pHuffBits[j-1];

        if (0==k) {
            /*  -1, if no codes of this length */
            pHuffTable->maxcode[j] = (Ipp16u) -1;
        } else {
            /* huffval[] index of 1st symbol of code length j */
            pHuffTable->valptr[j]  = (Ipp16u)p;
            /* minimum code of length j */
            pHuffTable->mincode[j] = (Ipp16u)huffcode[p];

            i = p + k;

            while (p<i) {
                pHuffTable->huffVal[p] = pHuffValue[p];
                p++;
            }
            /* maximum code of length j */
            pHuffTable->maxcode[j] = (Ipp16u)huffcode[p-1];
        } /* if (0==k) */
    } /* for (p=0, j=1; j<=16; j++) */
        
    pHuffTable->maxcode[17] = (Ipp16u) -1;

    /* memset(pHuffTable->lookBitsVal, 0, 256*sizeof(Ipp32u)); */

    for (i=0; i<256; i++) {
        pHuffTable->lookBitsVal[i]=0;
    }

    for (p=0, j=1; j<=8; j++) {
        k = (int)pHuffBits[j-1];
        for (i=1; i<=k; i++,p++) {
            lookbits = huffcode[p]<<(8-j);
            for (ctr=1<<(8-j); ctr > 0; ctr--) {
                pHuffTable->lookBitsVal[lookbits] = (j<<16) | (pHuffValue[p]);
                lookbits++;
            }
        }/* for (i=1; i<=k; i++,p++) */
    } /* for (p=0, j=1; j<=8; j++) */

    return IPP_STATUS_OK;
}

/* EOF */
